package demo15;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test {
    public static void main(String[] args) {
//        int[] nums = {-1,0,1,2,-1,-4};
        int[] nums = {0,0,0,0,0,0,0,0};
        System.out.println(threeSum(nums));


    }

    public static List<List<Integer>> threeSum(int[] nums) {
        //父结果集，用来装所有子结果集
        List<List<Integer>> father = new ArrayList<>();
        if(nums.length<3){
            //数组中不足3个数，肯定没有符合的结果集
            return father;
        }else {
            //对数组进行排序，从小到大
            Arrays.sort(nums);
        }
        if(nums[0]>0){
            //数组中最小的数都大于0，肯定没有符合的结果集
            return father;
        }
        //子结果集，用来装每次3个数的结果
        List<Integer> son;
        int left,right;//定义左指针和右指针
        //从左边开始扫描，先确定符合的结果集中，第一个数一定是i所指向的数
        for (int i = 0; nums[i] <= 0 && i < nums.length-2; i++) {
            if(i!=0 && nums[i] == nums[i-1]){
                continue;
            }
            //当i指向正数的时候，后续的结果集不可能符合结果，所以条件判断写nums[i] <= 0
            left = i+1;//重新给左指针赋值
            right = nums.length-1;//重新给右指针赋值
            while (left < right){
                //开始对i，left，right所指向的数做判断
                if(nums[i]+nums[left]+nums[right] == 0){
                    if(nums[right] == nums[right-1] && nums[left] == nums[left+1] && right-1 > left+1) {
                        //重复的结果集，不需要
                        right--;
                        left++;
                        continue;//退出此次循环，进入下一轮
                    }
                    //找到了对应的解，直接放进父结果集之后，创建新的子结果集去收集新的结果
                    son = new ArrayList<>();
                    son.add(nums[i]);
                    son.add(nums[left]);
                    son.add(nums[right]);
                    father.add(son);
                    left++;
                    right--;
                }else if(nums[i]+nums[left]+nums[right] < 0){
                    left++;//因为三个数的合小于0，将左指针指向的数右移变大
                }else if(nums[i]+nums[left]+nums[right] > 0){
                    right--;//因为三个数的合大于0，将右指针指向的数左移变小
                }
            }
        }
        return father;
    }

}
